package everydayone.lfuCache;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @Date 2020/04/05
 * @author 王光浩 
 * @Thinking 使用暴力法
 * @Analysis 时间复杂度O（n*操作数），空间复杂度O（n）——每次get和put操作都是O（n）级别的
 */
public class MyMethodOne {
	private HashMap<Integer,Integer> keyValue; //存储键值对
	private HashMap<Integer,Integer> keyCount; //存储键使用次数
	private LinkedList<Integer> lastUser;           //按最近被使用顺序存储
	private int capaci;                        //记录最大容量
	private int now;                           //记录当前被使用的容量
	public MyMethodOne(int capacity) {
		keyValue=new HashMap<Integer,Integer>();
		keyCount=new HashMap<Integer,Integer>();
		lastUser=new LinkedList<Integer>();
		capaci=capacity;
		now=0;
    }
    
    public int get(int key) {
    	if(!keyValue.containsKey(key))return -1;
    	//将key移动到最近使用队列的开始处 O(n)
    	lastUser.remove(Integer.valueOf(key));
    	lastUser.add(key);
    	//更新使用次数
    	keyCount.put(key, keyCount.get(key)+1); 
    	return keyValue.get(key);
    }
    
    public void put(int key, int value) {
    	if(capaci==0)return;
    	int count=1;
    	if(keyValue.containsKey(key)) {
    		count=keyCount.get(key);
    		keyValue.remove(key);
    		keyCount.remove(key);
    		lastUser.remove(Integer.valueOf(key));
    		now--;
    	}
    	if(now==capaci) { //时间复杂度O（1）
    		int minCount=Integer.MAX_VALUE;
    		//找出最小出现次数的key
    		for(int tem :keyCount.values()) { //时间复杂度O（n）
    			if(tem<minCount) minCount=tem;
    		}
    		//在最近使用队列中找出对应value为最小出现次数的第一个key
    		int removeKey=0;
    		for(int tem:lastUser) {   //时间复杂度O（n）
    			if(keyCount.get(tem)==minCount) {
    				removeKey=tem;
    				break;
    			}
    		}
    		//删除 removeKey，然后将新的元素插入
    		keyValue.remove(removeKey);
    		keyCount.remove(removeKey);
    		lastUser.remove(Integer.valueOf(removeKey)); //时间复杂度O（n）
    	}
    	else now++;
    	keyValue.put(key, value);
		keyCount.put(key, count+1);
		lastUser.add(key);
    }
}
